package LinkedList.反转链表_区间;

import LinkedList.ListNode;

public class Test {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode cur = dummy;
        // 找到要反转的前一个节点
        for(int i = 1; i < left; i++) {
            cur = cur.next;
        }
        // 找到要反转的链表的第一个和最后应该节点
        ListNode start = cur.next;
        ListNode end = cur.next;
        for(int i = left; i < right; i++) {
            end = end.next;
        }
        // 保留 end 后面的节点
        ListNode next = end.next;
        end.next = null;
        // 开始反转
        cur.next = reverseList(start);
        start.next = next;

        return dummy.next;
    }

    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        while(cur != null) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }


}
